package com.company.笔试.快排;

import java.util.Arrays;

/**
 * @author ylr
 * @version 1.0.0
 * @ClassName Solution.java
 * @Description TODO
 * @createTime 2022年02月24日 14:22:00
 */
public class Solution {
    public static void main(String[] args) {
        int[] list = new int[]{7,2,5,9,2,34,4};
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.quickSort(list, 0, list.length - 1)));
    }

    public int[] quickSort(int[] list, int left, int right) {
        if (left<right){
            int mid = findMid(list, left, right);
            quickSort(list,left,mid-1);
            quickSort(list,mid+1,right);
        }
        return list;
    }

    public int findMid(int[] list, int left, int right) {
        int mid = list[left];
        while (left < right) {
            while (left < right) {
                if (list[right] >= mid) {
                    right--;
                } else {
                    list[left] = list[right];
                    left++;
                    break;
                }
            }
            while (left < right) {
                if (list[left] <= mid) {
                    left++;
                } else {
                    list[right] = list[left];
                    right--;
                    break;
                }
            }
        }
        list[left] = mid;
        return left;
    }

}
